package com.chilly.linkedlist;

import com.chilly.utils.LinkedListUtil;
import com.chilly.utils.ListNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 148. 排序链表
 * <p>
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * <p>
 * Created by Chilly Cui on 2020/12/1.
 */
public class SortList {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(4);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        listNode.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = null;

        ListNode node = new Solution().sortList(listNode);
//        LinkedListUtil.printLink(node);
    }


    static class Solution {
        ListNode newHead = new ListNode();

        public ListNode sortList(ListNode head) {
            List<Integer> list = new ArrayList<>();
            while (head != null) {
                list.add(head.val);
                head = head.next;
            }
            Collections.sort(list);

            for (Integer val : list) {
                add(val);
            }
            return newHead;
        }

        public void add(Integer data) {
            ListNode newnode = new ListNode(data);
            if (newHead == null) {
                newHead = newnode;
                return;
            }
            ListNode temp = newHead;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newnode;
        }
    }
}
